package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/">1218. 最长定差子序列</a>
 */
public class Solution1218 extends BaseSolution {

    public int longestSubsequence(int[] arr, int difference) {
        int[] flag = new int[20001];
        for (int v : arr) {
            int ind = v + 10000;
            int pre = ind - difference;
            flag[ind] = Math.max(flag[ind], (pre >= 0 && pre < flag.length ? flag[pre] : 0) + 1);
        }
        int max = 0;
        for (int v : flag) {
            max = Math.max(v, max);
        }
        return max;
    }

    public static void main(String[] args) {
        Solution1218 solution = new Solution1218();
        System.out.println(solution.longestSubsequence(new int[] {
                1,5,7,8,5,3,4,2,1
        }, -2));
    }
}